{--
    Frequently used functions and values used in Project Euler
    http://projecteuler.net/
-}
package examples.EulerLib where

import Data.List
-- import Prelude.Floating

--- Overloaded values and operations on integers
class  (Show a, Integral a, Enum a) => Natural a where
    --- product
    prod :: [a] -> a
    prod xs = fold (*) one xs
    
    --- sum
    summe :: [a] -> a
    summe  xs = fold (+) zero xs
    
    --- the list of prime numbers
    primes :: [a]
    primes = fromInt 2 : filter isPrime (iterate (fromInt 2 +) (fromInt 3))
    
    --- predicate to check if a number is prime
    isPrime :: a -> Bool
    

    
    --- primefactors in descending order, duplicates are retained.
    factors :: a -> [a]
    factorsLoop :: [a] -> a -> [a] -> [a]
    
    --- primefactors where equal factors are replaced by their product
    factorProducts :: a -> [a]
    
    -- canonicFactors come in the form (n, f) where _n_ is how often _f_ is used
    --- 'divisors' of a number (including 1 and the number itself)
    --- 'properDivisors' are the 'divisors' excluding the number itself
    divisors, properDivisors :: a -> [a]
    
    divisors n 
          | n <  zero = divisors (abs n)
          | n == zero = []
          | n == one  = [n]
          | otherwise = goDivisors n (succ one) [one,n]
    private goDivisors :: a -> a -> [a] -> [a]
    private goDivisors n i acc = case i*i of
        !sqr | sqr > n           = acc
             | sqr == n          = i:acc
             | n `rem` i == zero = goDivisors n (succ i) (i : n `quot` i : acc)
             | otherwise         = goDivisors n (succ i) acc
             
    properDivisors n = filter (n!=) (divisors n) 
    
    isPrime n = n > fromInt 1 && primePred n primes
    private primePred :: a -> [a] -> Bool
    primePred n (a:as)
            | a*a > n          = true
            | n `rem`a == zero = false
            | otherwise        = primePred n as
    primePred n []             = true       -- to avoid a throws clause
    factors n
            | abs n < 2 = []
            | otherwise = factorsLoop primes (abs n) []
    private factorsLoop (a:as) !n !acc
            | a*a > n           = n:acc
            | n `rem` a == zero = factorsLoop (a:as) (n `quot` a) (a:acc)
            | otherwise         = factorsLoop as n acc
    private factorsLoop _ _ _              = []            -- avoid throws clause
    
    factorProducts = map prod . group . factors
    
    --- nowarn: is not easy enough
    {-- check if _n_ is a square and if so return 'Right' _k_
        where _k²_ = _n_, otherwise 'Left' _k_ where _k² < n_
    -}
    isSquare :: a -> Either a a 
    isSquare n 
        | n > fromInt 10 = loop zero (n `quot` fromInt 4) (n `quot` fromInt 2)
        | n == fromInt 10 = Left  (fromInt 3)
        | n == fromInt  9 = Right (fromInt 3)
        | n <= fromInt  8,
          n >= fromInt  5 = Left  (fromInt 2)
        | n == fromInt  4 = Right (fromInt 2)
        | n <= fromInt  3,
          n >= fromInt  2 = Left  one
        | n == one        = Right one
        | n == zero       = Right zero
        | otherwise       = error ("isSquare argument negative " ++ show n)
        where
            loop a b c
               | b2 == n             = Right b
               | a >=  c             = left b
               | a ==  b, b+one == c = Left b
               | b2 >  n             = loop a ((a+b) `quot` fromInt 2) b
               | otherwise           = loop b ((b+c) `quot` fromInt 2) c
               where !b2 = b*b
                     left b | b*b < n = Left b
                            | otherwise = left (b-one)




instance Natural Int
instance Natural Long
instance Natural Integer
